import common.ListNode;

import java.util.PriorityQueue;

/**
 * 23. Merge k Sorted Lists 合并K个升序链表
 * https://leetcode.cn/problems/merge-k-sorted-lists/description/
 */
class MergeKLists {
    /**
     * 方法：合并K个有序链表
     * 使用优先队列来存储当前K个链表的头节点，根据节点的值排序。每次从队列中取出最小的节点，并将其下一个节点加入队列中。
     * 
     * Args:
     *   lists: ListNode[] - K个升序链表的头节点数组
     * 
     * Returns:
     *   ListNode - 合并后的升序链表的头节点
     * 
     * Time: O(N*logk) - N是所有链表中元素的总和，k是链表个数。需要进行N次插入和删除操作，每次操作的时间复杂度是O(logk)
     * 
     * Space: O(k) - 需要一个大小为k的优先队列来存储当前K个链表的头节点
     */
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for(ListNode head : lists){
            if(head != null){
                pq.offer(head); // 把所有非空链表的头节点入堆
            }
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while(!pq.isEmpty()){
            ListNode node = pq.poll();
            if(node.next != null){
                pq.offer(node.next);
            }
            cur.next = node;
            cur = cur.next;
        }
        return dummy.next;
    }
}